{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Total Number of Colored Cells"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: coloredCells"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计染色格子数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一个无穷大的二维网格图，一开始所有格子都未染色。给你一个正整数&nbsp;<code>n</code>&nbsp;，表示你需要执行以下步骤&nbsp;<code>n</code>&nbsp;分钟：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>第一分钟，将 <strong>任一</strong> 格子染成蓝色。</li>\n",
    "\t<li>之后的每一分钟，将与蓝色格子相邻的 <strong>所有</strong> 未染色格子染成蓝色。</li>\n",
    "</ul>\n",
    "\n",
    "<p>下图分别是 1、2、3 分钟后的网格图。</p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/01/10/example-copy-2.png\" style=\"width: 500px; height: 279px;\">\n",
    "<p>请你返回 <code>n</code>&nbsp;分钟之后 <strong>被染色的格子&nbsp;</strong>数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>示例 1：</b></p>\n",
    "\n",
    "<pre><b>输入：</b>n = 1\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>1 分钟后，只有 1 个蓝色的格子，所以返回 1 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>n = 2\n",
    "<b>输出：</b>5\n",
    "<b>解释：</b>2 分钟后，有 4 个在边缘的蓝色格子和 1 个在中间的蓝色格子，所以返回 5 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-total-number-of-colored-cells](https://leetcode.cn/problems/count-total-number-of-colored-cells/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-total-number-of-colored-cells](https://leetcode.cn/problems/count-total-number-of-colored-cells/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1', '2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coloredCells(self, n: int) -> int:\n",
    "        return 2*n*(n-1) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coloredCells(self, n: int) -> int:\n",
    "        ans=1\n",
    "        for i in range(n-1):\n",
    "            ans+=4*(i+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coloredCells(self, n: int) -> int:\n",
    "        return n**2 + (n-1)**2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coloredCells(self, n: int) -> int:\n",
    "        return 2 * n * n - 2 * n + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coloredCells(self, n: int) -> int:\n",
    "        return 2 * n * n - 2 * n + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coloredCells(self, n: int) -> int:\n",
    "        return 1 + 2 * n * (n - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coloredCells(self, n: int) -> int:\n",
    "        return 2*n*n - (2*n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coloredCells(self, n: int) -> int:\n",
    "        return 1 + sum([4*i for i in range(n)])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coloredCells(self, n: int) -> int:\n",
    "        ans=[2*i for i in range(1,2*n,2)]\n",
    "        return(sum(ans)-2*n+1)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coloredCells(self, n: int) -> int:\n",
    "        return sum([4*i for i in range(n)])+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coloredCells(self, n: int) -> int:\n",
    "        list_ = [1]\n",
    "        if n == 1:\n",
    "            return list_[n-1]\n",
    "        for i in range(2, n+1):\n",
    "            num = list_[-1] + i + i - 1 + i - 1 + i - 2\n",
    "            list_.append(num)\n",
    "        return list_[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coloredCells(self, n: int) -> int:\n",
    "        dp=[1]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            dp[i]=dp[i-1]+4*i-4\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coloredCells(self, n: int) -> int:\n",
    "        dp = [0] * n\n",
    "        dp[0] = 1\n",
    "        for i in range(1, n):\n",
    "            dp[i] = dp[i-1] + 4 * (i+1) - 4\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coloredCells(self, n: int) -> int:\n",
    "        if n == 1: return 1\n",
    "        if n == 2: return 5\n",
    "        li = [i for i in range(1, 2 * (n - 1), 2)]\n",
    "        return sum(li) * 2 + 2 * n - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "d = [0] * 100001\n",
    "def help():\n",
    "    d[1] = 1\n",
    "    d[2] = 5\n",
    "    d[3] = 13\n",
    "    for i in range(4, 100001):\n",
    "        d[i] = 1 + 4 * (i - 1) + (1 + i - 2) * (i - 2) // 2 * 4\n",
    "help()\n",
    "class Solution:\n",
    "    def coloredCells(self, n: int) -> int:\n",
    "        return d[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coloredCells(self, n: int) -> int:\n",
    "        dp = [0 for _ in range(n)]\n",
    "        dp[0] = 1\n",
    "        for i in range(1, n):\n",
    "            dp[i] = dp[i - 1] + 4 * (i + 1) - 4\n",
    "        return dp[n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coloredCells(self, n: int) -> int:        \n",
    "        dp = [0 for i in range(n+1)]\n",
    "        dp[1] = 1\n",
    "        \n",
    "        for i in range(2,n+1):\n",
    "            dp[i] = dp[i-1]+ 4*(i-1)\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coloredCells(self, n: int) -> int:\n",
    "        if n==1:\n",
    "            return 1\n",
    "        dp = [0 for i in range(n+1)]\n",
    "        dp[0] = 0\n",
    "        dp[1] = 1\n",
    "        for i in range(2,n+1):\n",
    "            dp[i] = dp[i-1] + 4 * (i-1)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coloredCells(self, n: int) -> int:\n",
    "        dp=[0 for _ in range(n)]\n",
    "        dp[0]=1\n",
    "        for i in range(1,len(dp)):\n",
    "            dp[i]=dp[i-1]+4*i\n",
    "        return dp[-1]            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "ans = [1]\n",
    "x = 4\n",
    "for i in range(100000):\n",
    "    ans.append(ans[-1] + x)\n",
    "    x += 4\n",
    "class Solution:\n",
    "    def coloredCells(self, n: int) -> int:\n",
    "        return ans[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coloredCells(self, n: int) -> int:\n",
    "        if n==1:\n",
    "            return 1\n",
    "        elif n==2:\n",
    "            return 5\n",
    "        dp=[0]*(n+1)\n",
    "        dp[1]=1\n",
    "        dp[2]=5\n",
    "\n",
    "\n",
    "        for i in range(3,n+1):\n",
    "            #print(dp[i-1])\n",
    "           # print(dp[i])\n",
    "            dp[i]=dp[i-1]+i*4-4\n",
    "\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coloredCells(self, n: int) -> int:\n",
    "        dp = [1] * (n + 1)\n",
    "        for i in range(2, n + 1):\n",
    "            dp[i] = dp[i - 1] + (i - 1) * 4\n",
    "        # print(dp)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coloredCells(self, n: int) -> int:\n",
    "        dp = [0]*n\n",
    "        if n==1:\n",
    "            return 1\n",
    "        if n==2:\n",
    "            return 5\n",
    "        dp[0] = 1\n",
    "        dp[1] = 5\n",
    "        for i in range(2,n):\n",
    "            dp[i] = dp[i-1] + 4*(i)\n",
    "        return dp[n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coloredCells(self, n: int) -> int:\n",
    "        dp=[0]*(n+1)\n",
    "        dp[1]=1\n",
    "        for i in range(2,n+1):\n",
    "            dp[i]=dp[i-1]+4*(i-1)\n",
    "        # print(dp)\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coloredCells(self, n: int) -> int:\n",
    "        if n == 1 :\n",
    "            return 1 \n",
    "        dp = [0]*(n+1)\n",
    "        dp[1] = 1\n",
    "        for i in range(2, n+1): \n",
    "            dp[i] = dp[i-1] + i*2 + (i-2)*2\n",
    "        \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coloredCells(self, n: int) -> int:\n",
    "        dp = [1]*n\n",
    "        for i in range(1, n):\n",
    "            dp[i] = dp[i-1]+4*(i)\n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coloredCells(self, n: int) -> int:\n",
    "        dp = [0]*(n+1)\n",
    "        dp[1] = 1\n",
    "        for i in range(2, n+1):\n",
    "            dp[i] = dp[i-1]+(i*2+(i-2)*2)\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coloredCells(self, n: int) -> int:\n",
    "        # return 2*(n-1)*n + 1\n",
    "        dp = [0]*(n+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(n):\n",
    "            dp[i+1] = dp[i] + 4*i\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coloredCells(self, n: int) -> int:\n",
    "       # 1 5 13 25\n",
    "       #  4 8 12\n",
    "        if n==1:\n",
    "            return 1\n",
    "\n",
    "        ans  = [0 ]*n\n",
    "        \n",
    "        ans[0] = 1\n",
    "        for i in range(1,n):\n",
    "            ans[i] = ans[i-1] +  4*i\n",
    "\n",
    "        return ans[-1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
